Corso di Laurea in Informatica Linguaggio e Metodi della Matematica: Prova scritta del 19 giugno2002 - N. 1

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

Esercizio 1. Si trovi una forma normale prenessa dell’enunciato

¬∀x[(∃y(x > y)) → x > 0]

e si stabilisca se esso costituisce una affermazione vera o falsa sui numeri naturali. Esercizio 2. Usando le notazioni logiche, le costanti numeriche 0, 1, 2, …, le operazioni di somma e prodotto, e la relazione ≤, si esprima l’enunciato

“C’è uno e un solo multiplo di 5 nell’intervallo tra 21 e 29”

Esercizio 3. Stabilire se le seguenti funzioni da Z^{2} ad Z sono iniettive, surgettive, biunivoche.

1. f(x, y) = 21x + 5y

2. g(x, y) = 3x + 6y. Esercizio 4. Si consideri l’insieme X = {1, 2, …, 20} dei numeri naturali compresi fra 1 e 20.

1. Quanti sono i sottoinsiemi di X che contengono esattamente 3 elementi dispari?

2. Quanti sono i sottoinsiemi di X che contengono almeno un multiplo di 5?

3. Quanti sono i sottoinsiemi A di X tali che A ∪ {1, 2, 3, 4, 5} = X? NOTA: la risposta va giustificata, ed è sufficiente indicare un’espressione algebrica, senza svolgere i conti. Esercizio 5. Determinare per quali valori dell’intero n la congruenza

21x ≡ 15 (mod 11n)

ha soluzione, e risolverla per n = 24. Esercizio 6. Sia f_{n} la successione definita per ricorrenza ponendo f_{0} = 3, f_{1} = 4, e f_{n+1} = (f_{n} + f_{n−1})/2.

1. Dimostrare che 3 ≤ f_{n} ≤ 4

2. Dimostrare che n ≥ 2 allora f_{n} è un razionale della forma \frac{r}{2^{n−1}} , con r dispari;

3. Definiamo una successione g_{n} ponendo g_{n} = f_{2n}. Dimostrare che la successione g_{n} è crescente.

Corso di Laurea in Informatica Linguaggio e Metodi della Matematica: Prova scritta del 19 giugno 2002 - N. 2

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

Esercizio 1. Si trovi una forma normale prenessa dell’enunciato

¬∀x[(∀y(x · y = 0)) → x = 0]

e si stabilisca se esso costituisce una affermazione vera o falsa sui numeri naturali. Esercizio 2. Usando le notazioni logiche, le costanti numeriche 0, 1, 2, …, le operazioni di somma e prodotto ed esponenziazione, e la relazione ≤, si esprima l’enunciato

“C’è una ed una sola potenza di due nell’intervallo tra 10 e 30.”

Esercizio 3. Stabilire se le seguenti funzioni da Z^{2} ad Z sono iniettive, surgettive, biunivoche.

1. f(x, y) = 5x + 15y

2. g(x, y) = 7x + 9y. Esercizio 4. Si consideri l’insieme X = {1, 2, …, 20} dei numeri naturali compresi fra 1 e 20.

1. Quanti sono i sottoinsiemi di X che contengono esattamente 6 numeri pari?

2. Quanti sono i sottoinsiemi di X che contengono almeno un multiplo di 4?

3. Quanti sono i sottoinsiemi A di X tali che A ∪ {5, 10, 15, 20} = X? NOTA: la risposta va giustificata, ed è sufficiente indicare un’espressione algebrica, senza svolgere i conti. Esercizio 5. Determinare per quali valori dell’intero n la congruenza

33x ≡ 21 (mod 7n)

ha soluzione, e risolverla per n = 15. Esercizio 6. Sia f_{n} la successione definita per ricorrenza ponendo f_{0} = 4, f_{1} = 3, e f_{n+1} = (f_{n} + f_{n−1})/2.

1. Dimostrare che 3 ≤ f_{n} ≤ 4

2. Dimostrare che se n ≥ 2 allora f_{n} è un razionale della forma \frac{r}{2^{n−1}} , con r dispari;

3. Definiamo una successione g_{n} ponendo g_{n} = f_{2n}. Dimostrare che la successione g_{n} è decrescente.

Corso di Laurea in Informatica Linguaggio e Metodi della Matematica: Prova scritta del 19 giugno 2002 - N. 3

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

Esercizio 1. Si trovi una forma normale prenessa dell’enunciato

¬∃x[(∃y(x < y)) → x = 0]

e si stabilisca se esso costituisce una affermazione vera o falsa sui numeri naturali. Esercizio 2. Usando le notazioni logiche, le costanti numeriche 0, 1, 2, …, le operazioni di somma e prodotto, e la relazione ≤, si esprima l’enunciato

“C’è uno e un solo cubo nell’intervallo di numeri interi tra 10 e 20.”

Esercizio 3. Stabilire se le seguenti funzioni da Z^{2} ad Z sono iniettive, surgettive, biunivoche.

1. f(x, y) = 2x + 4y

2. g(x, y) = 4x + 3y. Esercizio 4. Si consideri l’insieme X = {1, 2, …, 24} dei numeri naturali compresi fra 1 e 24.

1. Quanti sono i sottoinsiemi di X che contengono esattamente 4 multipli di 3?

2. Quanti sono i sottoinsiemi di X che contengono almeno un multiplo di 6?

3. Quanti sono i sottoinsiemi A di X tali che A ∪ {4, 8, 12, 16, 20, 24} = X? NOTA: la risposta va giustificata, ed è sufficiente indicare un’espressione algebrica, senza svolgere i conti. Esercizio 5. Determinare per quali valori dell’intero n la congruenza

39x ≡ 21 (mod 5n)

ha soluzione, e risolverla per n = 18. Esercizio 6. Sia f_{n} la successione definita per ricorrenza ponendo f_{0} = 3, f_{1} = 4, e f_{n+1} = (f_{n} + f_{n−1})/2.

1. Dimostrare che 3 ≤ f_{n} ≤ 4

2. Dimostrare che se n ≥ 2 allora f_{n} è un razionale della forma \frac{r}{2^{n−1}} , con r dispari;

3. Definiamo una successione g_{n} ponendo g_{n} = f_{2n+1}. Dimostrare che la successione g_{n} è decrescente.

Corso di Laurea in Informatica Linguaggio e Metodi della Matematica: Prova scritta del 19 giugno 2002 - N. 4

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

Esercizio 1. Si trovi una forma normale prenessa dell’enunciato

¬∃x[(∀y(x + y = 0)) → x = 0]

e si stabilisca se esso costituisce una affermazione vera o falsa sui numeri naturali. Esercizio 2. Usando le notazioni logiche, le costanti numeriche 0, 1, 2, …, le operazioni di somma e prodotto, e la relazione ≤, si esprima l’enunciato

“C’è uno ed un solo quadrato tra gli interi compresi tra 10 e 20.”

Esercizio 3. Stabilire se le seguenti funzioni da Z^{2} ad Z sono iniettive, surgettive, biunivoche.

1. f(x, y) = 6x + 5y

2. g(x, y) = 3x + 12y. Esercizio 4. Si consideri l’insieme X = {1, 2, …, 24} dei numeri naturali compresi fra 1 e 24.

1. Quanti sono i sottoinsiemi di X che contengono esattamente 2 multipli di 6?

2. Quanti sono i sottoinsiemi di X che contengono almeno un multiplo di 3?

3. Quanti sono i sottoinsiemi A di X tali che A ∪ {1, 2, 3, 4, 5, 6} = X? NOTA: la risposta va giustificata, ed è sufficiente indicare un’espressione algebrica, senza svolgere i conti. Esercizio 5. Determinare per quali valori dell’intero n la congruenza

24x ≡ 39 (mod 11n)

ha soluzione, e risolverla per n = 15. Esercizio 6. Sia f_{n} la successione definita per ricorrenza ponendo f_{0} = 4, f_{1} = 3, e f_{n+1} = (f_{n} + f_{n−1})/2.

1. Dimostrare che 3 ≤ f_{n} ≤ 4

2. Dimostrare che se n ≥ 2 allora f_{n} è un razionale della forma \frac{r}{2^{n−1}} , con r dispari;

3. Definiamo una successione g_{n} ponendo g_{n} = f_{2n+1}. Dimostrare che la successione g_{n} è crescente.